Міністерство освіти та науки України
Національний університет „Львівська політехніка”
кафедра прикладної математики
з курсу „Дискретна математика”
на тему:
„Знаходження числа впорядкованих і невпорядкованих вибірок з повторенням”
Зміст
Вступ…………...................................................................................3
1. Перестановки…………......................................................................4
2. Розміщення………..........................................................................7
3. Комбінації……………………………...……...............................14
4. Список використаної літератури ................................................17
Вступ
Вибірка, вибір… Це явище знайоме, мабуть, кожній дорослій людині. Воно для нас швидще психологічного характеру, адже в житті кожного приходиться ставити перед собою певний вибір. Але в даній роботі йтиметься не про вищезгаданий „страшний фатум”, а про математичний вибір. Саме з таких, на перший погляд, простих речей розпочинався розвиток математичних наук. Дуже важливим є поняття вибірок для сучасного програмування, що є прийнятним і цікавим для мене особисто.
Як відомо, існує кілька різновидів вибірок (сукупності елементів або речей, які не обов’язково повинні мати спільні властивості), таких як вибірка із поверненням, вибірка без повернення, число комбінацій, число перестановок і навіть частково сюди можна віднести поняття „факторіалу”. Дана праця несе досить таки непогано висвітлені (як на мою думку) приклади із застосуванням даних понять і окремих задач, в основі яких всюди присутня одна спільна тема – вибірка.
1. Перестановки
Означення 1.1. Нехай впорядковується (задається порядок елементів) множина М* потужності п, яка не є різноелементною і містить k1 елементів 1-го типу, k2 елементів 2-го типу, ..., ks елементів s-го типу (k1+k2+…+ks=n) причому елементи однакового типу вважаються невідрізнимими.
Одержану при цьому впорядковану множину називають перестановкою з п елементів з повторенням.
Через наявність однакових елементів не всі перестановки з повторенням будуть різними (відрізнимими), тому виникає питання про визначення кількості лише відрізнимих перестановок.
Потужність множини всіх відрізнимих перестановок з повторенням з n елементів, про які йдеться в означенні 1.1, позначається символом Сn (k1,k2,…,k).
Надалі слово "відрізнимі" будемо опускати, розуміючи, що саме такі перестановки з повторенням і маються на увазі.
За допомогою ОПК (основного правила комбінаторики), доведемо формулу обчислення Сn (k1, ,k2,...,ks).
Розглянемо скінченну множину М * , яка не є різноелементною і має k1, однакових елементів 1-го типу, k2 однакових елементів 2-го типу, ..., ks однакових елементів s-го типу (k1+k2+…+ks=n). Скільки відрізнимих перестановок має множина М*?
Якби множина М * була різноелементною, то вона мала б п! відрізнимих перестановок. Насправді внаслідок наявності однакових елементів деякі перестановки будуть невідрізнимими, тому їх треба об'єднувати в один клас і рахувати як одну перестановку. Обчислимо потужність такого класу.
Нехай - довільна фіксована перестановка множини М *. Якщо в перестановці довільно поміняти місцями лише елементи 1-го типу (перша дія D1, число способів її виконання ), потім - лише елементи 2-го типу (друга дія D2, число способів її виконання )…, лише елементи s-гo типу (s-та дія Ds, число способів її виконання ), то
отримаємо невідрізниму від неї перестановку. Їх загальна кількість за ОПК становитиме число k1!∙k2! ∙ ∙ ∙ ks! (у це число включається і ).
Для іншої перестановки відрізнимої від , також буде
k1!∙k2! ∙ ∙ ∙ ks! невідрізнимих від неї перестановок і т.д.
Отже, сукупність з n! перестановок множини M* розкладається на класи невідрізнимих перестановок, ці класи попарно не перетинаються і мають однакову потужність, яка дорівнює k1!∙k2! ∙ ∙ ∙ ks!
Отже, відрізнимих перестановок множини М* буде стільки, скільки є класів, тобто
...
